import java.util.ArrayList;
import java.util.List;

public class Test30 {
    public final  static class MaxHeap<T extends Comparable<T>>{
        private List<T> items;
        private int cursor;
        private int count = 0;
        public MaxHeap() {
            this(32);//初始化为一个32的堆
        }

        /**
         * 自定义大小
         * @param size
         */
        public MaxHeap(int size) {
            items = new ArrayList<>(size);
            cursor = -1;
        }
        /**
         * 向上调整堆
         *
         * @param index 被上移元素的起始位置
         */
        public void siftup(int index){//根结点
            T intent = items.get(index); //获取需要调整的元素
            while (index > 0){
                int parentIndex = (index-1)/2; //找到父节点
                T parent = items.get(parentIndex);
                if (intent.compareTo(parent) >0){
                    //如果元素大于父节点，则替换父节点，把父节点往下放放
                    items.set(index,parent);//把index替换为父节点的值
                    index = parentIndex;//index指向父节点的索引
                }else break;
                items.set(index,intent);//都对比结束，把itennt放入
            }
        }

        /**
         * 向下调整
         * @param index
         */
        public void siftDown(int index){
            T intent = items.get(index);
            int childleft = index*2+1;
            while(childleft  < items.size()){
                int maxindex = childleft;
                T maxChild = items.get(childleft);//左节点对象
                int rigthindex = childleft + 1;//右节点索引
                if (rigthindex < items.size()){
                    T rightChild = items.get(rigthindex);//右节点的对象
                    if (rightChild.compareTo(maxChild) > 0){
                        maxChild = rightChild;
                        maxindex = rigthindex;
                    }
                }
                if (maxChild.compareTo(intent) > 0){
                    items.set(index,maxChild);
                    index = maxindex;//记录上移节点位置
                    childleft  = index*2+1;
                }else break;
            }
            items.set(index,intent);
        }

        public void add(T item){
            items.add(item);
            count ++;
            siftup(items.size()-1);
        }

        /**
         * 删除堆顶元素
         * @return
         */
        public T deleteTop(){
            if (items.isEmpty()) throw new RuntimeException("empty");

            T maxItem = items.get(0);//获取堆顶元素
            T lastItem = items.remove(items.size()-1);//删除最后一个元素
            if (items.isEmpty()) return lastItem;
            //如果删除最后一个元素，没有空，继续向下调整
            items.set(0,lastItem);
            siftDown(0);
            return maxItem;
        }

        /**
         * 获取下一个元素
         * @return
         */
        public T next(){
            cursor ++;
            if (cursor >= items.size()){
                throw new RuntimeException("No more element");
            }
            return items.get(cursor);
        }

        /**
         * 堆中是否还有下一个元素
         * @return
         */
        public boolean hasNext(){
            cursor ++;
            return  cursor<items.size();
        }

        public T first(){
            if (isEmpty()) throw new RuntimeException("The heap is empty.");
            return items.get(0);
        }

        public int size(){
            return items.size();
        }

        public String toString(){
            return  items.toString();
        }

        //判断是否已满
        public boolean full(){
            if (count >= size()) return true;
            else return false;
        }

        public boolean isEmpty(){
            return items.isEmpty();
        }

        /**
         * 清空堆
         */
        public void clear() {
            items.clear();
        }
    }

    /**
     * 第一种解法
     * @param input
     * @param output
     */
    public static void geLeastNumber1(int[] input,int[] output){
        if (input == null || output == null || output.length < 1 || input.length < 1) throw new IllegalArgumentException("Invalid");
        MaxHeap<Integer> maxHeap = new MaxHeap<>(output.length);//构造一个大顶堆
        for (int i : input){
            if (maxHeap.size() < output.length){
                maxHeap.add(i);
            }else {
                int max = maxHeap.first();
                if (max > i){
                    maxHeap.deleteTop();
                    maxHeap.add(i);
                }
            }
        }
        for (int i =0; i< maxHeap.size();i++){
            output[i] = maxHeap.next();
        }
    }

    public static void geLeastNumber2(int[] input,int[] output){
        if (input == null || output == null || output.length < 1 || input.length < 1) throw new IllegalArgumentException("Invalid");
        int start = 0;
        int end = input.length-1;
        int index = partition(input,start,end);
        int target = output.length-1;
        while(index != target){
            if (index <= target) start  = index+1;
            else end = index-1;
            index = partition(input,start,end);
        }
        System.arraycopy(input, 0, output, 0, output.length);
    }

    public static int partition(int[] input, int start, int end){
        int temp = input[start];
        while(start < end){
            while (start<end && input[end] >= temp){
                end --;
            }
            input[start] = input[end];
            while (start < end && input[start] <= temp){
                start ++;
            }
            input[end] = input[start];
        }
        input[start] = temp;
        return start;

    }

    public static void main(String[] args) {
        System.out.println("第一种解法：");
        int[] data = {4, 5, 1, 6, 2, 7, 3, 8};

        int[] output = new int[4];
        geLeastNumber2(data, output);
        for (int i : output) {
            System.out.print(i + " ");
        }
        System.out.println();


    }
}
